package day02;

/**
 * @author Jetwang
 * @version 1.0
 * @since 2023/3/2 14:31
 * 杨辉三角形
 */

public class YangHuiTrianglePlus {
    private static int element(int[][] triangle, int i, int j) {
        if (j == 0 || j == i) {
            triangle[i][j] = 1;
            return 1;
        }
        if (triangle[i][j] != 0) {
            return triangle[i][j];
        }
        triangle[i][j] =  element(triangle,i - 1, j - 1) + element(triangle, i - 1, j);
        return triangle[i][j];
    }

    public static void createRow(int[] row, int i) {
        if (row[i] > 0) { // 此行已经经过计算，无需递归
            return;
        }
        if (i == 0) {
            row[0] = 1;
            return;
        }
        createRow(row, i-1); // 计算上一行
        for (int j = i; j > 0; j--) {
            row[j] = row[j] + row[j - 1];
        }
    }

    public static void print2(int n) {
        int[] row = new int[n];
        for (int i = 0; i < n; i++) {
            createRow(row, i);
            printSpace((n - 1 - i) * 2);
            for (int j = 0; j <= i; j++) {
                System.out.printf("%-4d", row[j]);
            }
            System.out.println();
        }
    }

    public static void printSpace(int n) {
        for (int i = 0; i < n; i++) {
            System.out.print(" ");
        }
    }

    public static void print(int n) {
        int[][] triangle = new int[n][];
        for (int i = 0; i < n; i++) {
            triangle[i] = new int[i + 1];
            printSpace((n - 1 - i) * 2);
            for (int j = 0; j <= i; j++) {
                System.out.printf("%-4d", element(triangle, i, j));
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        // System.out.println(element(4, 2));
        // print(5);
        print2(5);
    }
}
